package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/sum-of-nodes-with-even-valued-grandparent/description
 *
 * 题型： 二叉树的前序遍历
 *
 * ```
 * 1315. 祖父节点值为偶数的节点和
 *
 * 给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：
 * 该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
 * 如果不存在祖父节点值为偶数的节点，那么返回 0 。
 *
 * 示例：
 * 输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
 * 输出：18
 * 解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。
 *
 * 提示：
 * 树中节点的数目在 1 到 10^4 之间。
 * 每个节点的值在 1 到 100 之间。
 * ```
 */
class leetcode_1315 {

    @Test
    fun test_1() {
        val n6 = TreeNode(6)
        val root = n6

        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        n6.left = n7
        n6.right = n8

        val n2 = TreeNode(2)
        val n7_2 = TreeNode(7)
        n7.left = n2
        n7.right = n7_2

        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        n8.left = n1
        n8.right = n3

        val n9 = TreeNode(9)
        n2.left = n9

        val n1_2 = TreeNode(1)
        val n4 = TreeNode(4)
        n7_2.left = n1_2
        n7_2.right = n4

        val n5 = TreeNode(5)
        n3.right = n5

        val actual = sumEvenGrandparent(root)
        val expected = 18
        Assert.assertEquals(expected, actual)
    }

    fun sumEvenGrandparent(root: TreeNode?): Int {
        /**
        题型： 二叉树的前序遍历

        思路：
        遍历节点时，传递父节点和祖父节点。判断当祖父节点不为空时，判断祖父节点是否为偶数，若是，则把累加当前节点

        时间复杂度：O(N)
        空间复杂度：O(1),递归函数占用的内存不计算在内。实际上只额外申请了一个sum。
         */
        collect(root, null, null)
        return sum
    }

    var sum: Int = 0
    fun collect(root: TreeNode?, parent: TreeNode?, grand: TreeNode?) {
        // 1 确定函数的参数以及返回值

        // 2 确定终止条件
        if (null == root) {
            return
        }

        // 3 确定单层递归的处理逻辑 : 前序遍历
        // 中
        grand?.let {
            // 当祖父节点不为空时，判断祖父节点是否为偶数，若是，则把累加当前节点
            if (it.`val` % 2 == 0) {
                sum = sum + root.`val`
            }
        }

        // 左
        collect(root.left, root, parent)

        // 右
        collect(root.right, root, parent)
    }
}